#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 040. 组合总和 II.py
@time: 2022/1/21 13:29
@desc: https://leetcode-cn.com/problems/combination-sum-ii/
> 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。 

@解题思路：
    1. 递归
    2. 含重复元素
    3. Ot(2^n*n), Os(n)
'''
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        n = len(candidates)
        candidates.sort()
        def backtrack(idx, target, path):
            if target==0:
                res.append(path)
            if target<0: return
            for i in range(idx, n):
                if candidates[i]>target: break
                # 如果有重复就跳过
                if i>idx and candidates[i]==candidates[i-1]: continue
                backtrack(i+1, target-candidates[i], path + [candidates[i]])
        res = []
        backtrack(0, target, [])
        return res